The Authentication and Key Agreement protocol (AKA) is a challenge-response based protocol that uses symmetric cryptography. The main goals of AKA include mutual authentication by two entities communicating with each other and establishment of cryptographic keys for protecting the communication exchanged in-between. A variant of AKA is the UMTS AKA, included in the security architecture standardized by 3GPP for 3G mobile communication networks in the Technical Specification 3G TS 33.102.
The basic concept of UMTS AKA is shown in FIG. 1. Referring to this figure, UMTS AKA protocol is run between a user equipment (UE) and a network entity (NE). The network entity initiates the AKA by sending a user authentication request to the UE. Along with the request, a random challenge, or random code (RAND), and an Authentication Token (AUTN) are sent to the UE. Upon receipt of the RAND and the AUTN, the UE, among other things, computes a Cipher Key (CK) and an Integrity Key (IK) and then uses them for ciphering and integrity functions.
The 3GPP is also undertaking the standardization of so-called “beyond-3G” communication networks. System Architecture Evolution (SAE) and Long Term Evaluation (LTE) are two closely-related aspects of the beyond-3G network. Compared with conventional 3G networks, a network based on SAE/LTE may impose higher and/or more security requirements. For instance, more cryptographic keys for securing the communication at different levels may be needed. The 3GPP has, in another standard-related document, 3GPP TR 33.821, recommended a key hierarchy for deriving more cryptographic keys for use in SAE/LTE.
FIG. 2 shows this key hierarchy. At the very top of the hierarchy is a key K, a long-term cryptographic key shared between the Universal Subscriber Identity Module (USIM of the UE and the Authentication Center (AuC) residing in the network. One level down is a pair of cryptographic keys CK and IK which are derived by the UE, particularly by the USIM thereof, in a same or similar manner as the UMTS AKA operation mentioned above. Further down in the hierarchy is a key KASME which is derived by the UE from CK, IK, and, if necessary, some other parameters. Once derived, KASME is transferred from AuC to the access network, particularly to the Access Securing Management Entity (ASME) of the SAE/LTE network, and then shared between the UE and the network. When the access network is based on LTE technology, the ASME's functionalities are handled by a Mobility Management Entity (MME).
The key KASME, and the keys “below” it in the hierarchy, may be derived by applying a certain cryptographic function. For instance,KASME=KDF(CK∥IK,0x02∥PLMN_ID∥<other_parameter>)where KDF is based on a Generic Bootstrapping Architecture (GBA) key derivation function (KDF). One GBA KDF is specified in 3G TS 33.220.
The GBA KDF may make use of cryptographic hash functions such as the Secure Hash Algorithm (SHA) hash functions. Among many SHA hash-functions, SHA-256 is a highly secure variant since it is considered collision resistant and acts like a pseudo-random function. As its name suggests, SHA-256 is a Secure Hash Algorithm hash function with a digest (output) length of 256 bits. The PLMN_ID is an identifier of the network serving the UE.
It has been realized that, in order to achieve a high-level of security, it is not sufficient to base the GBA KDF function mainly on CK and IK only. The rationale for this is the risk that a given UE might get the same CK twice, or two different UEs may get the same CK. In such cases, the “uniqueness” of the inputs to the KDF is undermined, and a collision between different UEs (using the same KASME) may occur.
As a general remark, while it is certain that KDF(x) produces the same key as KDF(y) if x=y, the converse may not always hold. That is, even if x≠y, it may still happen that KDF(x)=KDF(y). However, this is an unlikely event since the KDF is recommended to be based on SHA-256 which, as mentioned, has been designed to be collision resistant. Thus, for the technique described herein, it can be safely assumed that KDF(x)=KDF(y) if and only if x=y. This assumption allows the technique described herein to be focused on assuring “uniqueness” of the inputs to the KDF.
The standardizing body of the GBA KDF specification (ETSI/SAGE, the Special Algorithm Group of Experts) has noted the above problem and recommended including the UE's Private User Identity (IMPI) in <other_parameter> to avoid collisions between different UEs. As a further recommendation, a random code such as the RAND may also be included in <other_parameter>. This is described in a liaison statement from ETSI/SAGE to 3GPP SA3 (in 3GPP document number S3-030219).
However, it has been found that the above recommendations still cannot guarantee the “uniqueness” of the inputs to the KDF. This can be seen from the below analysis of the security property of the GBA KDF function and its usage in SAE/LTE for one and the same UE (e.g. one and the same IMPI).
Firstly, the following basic construction is considered:KDF(CK,IMPI).Since it has been assumed that IMPI=IMPI′ (when the UE is fixed), this basic construction will lead to collision for two inputs (CK, IMPI), (CK′,IMPI′) if and only if CK=CK′.
Secondly, another construction is considered, which is closer to the actual GBA KDF:KDF(CK∥IK,IMPI).
However, including IK into the inputs does not change the above collision property as one might believe at first. That is, KDF(CK∥IK, IMPI) will be equal to KDF(CK′∥IK′, IMPI) if and only if CK=CK′. To understand why including IK would not help, it is necessary to consider how CK and IK are produced by the cryptographic algorithm executed on the UE.
A typical UE-side cryptographic algorithm is the Milenage algorithm which is shown in FIG. 9. In FIG. 9, Ek denotes the Advanced Encryption Standard (AES) algorithm, also known as the Rijndael algorithm, using key K (stored in the AuC and USIM of UE). Consider now what happens if CK=CK′. Since AES is a permutation (a one-to-one mapping), this implies that the intermediate value (occurring at the fat arrow) is a uniquely determined by the outcome of f3 which happens to be CK. But this implies that the value at the fat arrow when producing CK must be the same as the value occurring at the same place when CK′ was produced. This in turn means that the values occurring as input to f4 must be the same and consequently, the same f4-values must occur. As it happens, f4 is IK. Thus it has been shown that CK=CK′ if and only if IK=IK′.
Next, an “improved” construction according to the recommendation of the standardizing body (SAGE), i.e., including RAND in the inputs, is considered:KDF(CK∥IK,RAND∥IMPI).
Assume that CK=CK′ (and thus IK=IK′). It is hoped that the use of RAND will guarantee uniqueness. However, this is not true. Consider again the “relevant” part of the Milenage algorithm that produced CK and IK from RAND: As shown in FIG. 9, there is a situation in which the value at the fat arrow corresponding to RAND is the same as that corresponding to RAND′. But again, AES (Ek) is a permutation so that the inputs must also be equal, i.e. RAND=RAND′. (The fact that AES is dependent on K does not help since a fixed UE is assumed and thus the same K will occur in both cases).
In other words, it has been shown that (CK∥IK, RAND∥IMPI)=(CK′∥IK′, RAND′∥IMPI) if and only if RAND=RAND′. In the SAE/LTE case, the PLMN_ID may also be included in the inputs, but since it is highly likely that the UE stays in the same network several times, this parameter PLMN_ID cannot be relied upon for the purpose of guaranteeing uniqueness.
An alternative approach to attempt to avoid collision could be to use another algorithm than AES for the cryptographic processing of the f3 and f4 algorithms. Specifically, the analysis above was based on the fact that AES is a permutation. It would therefore be possible to use a non-permutation (many-to-one mapping) instead of AES. This is problematic for two reasons. First of all, existing USIM's must be adapted to be suitable for the 3GPP SAE architecture. Secondly, by choosing a non-permutation function, one actually increases the probability that two outputs of e.g. f3 will collide.
The lack of uniqueness of the inputs can be a serious security issue. Since collision will occur if and only if RAND=RAND′, and since RAND is 128 bits, the collision is expected to occur after about 2^(128/2)=2^64 authentications (this is the so-called “birthday paradox”). Clearly, this is lower than the targeted security level of GBA (which is 128 bits). For LTE the case is even worse, since LTE is required to provide a security level of 256 bits. Thus, the high collision probability is a significant obstacle to providing the required security level in SAE/LTE.